//
// Created by Semir on 2020/5/17.
//

#include <iostream>
#include <string>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void Serialize(TreeNode* root, string& str) {
    if (root == nullptr) {
        str += "_#";
        return;
    }
    str += "_";
    str += std::to_string(root->val);
    Serialize(root->left, str);
    Serialize(root->right, str);
}

char* Serialize(TreeNode *root) {
    string str;
    Serialize(root, str);
    return (char*) str.c_str();
}

void Deserialize(TreeNode* root, string& str, int& index) {
    if (index < str.length()) {
        root = new TreeNode(str[index] - '0');

    }
}

TreeNode* Deserialize(char *str) {
    string sStr = str;
    TreeNode* root = nullptr;
    int index = 1;
    if (index < sStr.length()) {
        root = new TreeNode(sStr[index] - '0');
        index += 2;
        Deserialize(root->left, sStr, index);
        Deserialize(root->right, sStr, index);
    }
    return root;
}

int main() {
    return 0;
}
